CWOI 20230524D 数数题

魔法题。

题意简述

给定一个长度为 $n-1$ 的数组 $a$ 和一个长度为 $n$ 的数组 $c$。从 $i=2$ 开始，到 $i=n$ 结束，将点 $i$ 随机地连到 $[1,i-1]$ 中的一个点 $j$，概率是 $\dfrac {a_j} {a_1+a_2+\dots+a_{i-1}}$，边权是 $c_i+c_j$。询问 $Q$ 次两个点 $u,v$ 之间的期望距离。

$n\in[1,10^6],Q\in[1,10^6]$。但感觉 $n=10$ 都很不可做的样子……

解题思路

求解树上距离的常用方法是什么？当然是：

其中，$\text{dep}(x)$ 定义为点 $x$ 到 $1$ 号结点的距离，$\text{LCA}(u,v)$ 指的是 $u,v$ 的最近公共祖先。

同理，我们可以用类似的方法求树上期望距离：

通过期望的线性性我们可以得到：

因此我们要求的东西就只有两个了：一个点的期望深度，以及两个点最近公共祖先的期望深度。

期望深度

下面我们要求一个点 $x$ 的期望深度。

先简化一下表达：设数组 $b,b_i=\sum\limits_{j=1}^i a_j$，换句话说，$b$ 是 $a$ 的前缀和。

枚举 $x$ 的祖先由浅到深分别是 $1,p_1,p_2,\ldots,p_m$：

（由于省略号的原因上式的点乘 ‘$\cdot$’ 符号被换成了叉乘 ‘$\times$‘，见谅）

显然 $c_1+c_x$ 项与 $p$ 无关，也因此它的概率一定是 $1$，我们可以把它提出来：

上式被框住的式子，变换一下可得：

我们发现上式枚举的 $p$ 中的每一个 $c_i$ 都乘上了整个 $p$ 的 $\dfrac{a_1}{b_{i-1}}$ 的积。那么可以枚举 $c_i$ 计算贡献，变成（注意得 $i\in p$ 才行）：

$i\in p$ 这个条件不太好处理。但是上式被框住的式子一定包含 $j=i$ 这一项，因此我们可以提出来算：

引理

对于一个数集 $S$：

证明

该等式左边相当于是从集合 $S$ 中选择一些数的乘积的和，总共有 $2^{|S|}$ 种选法。而右边式子的意义就是“选”（“$S_i$”) 还是“不选”（”$1$“）。

证毕。

回到正题，式子 $(8)$被框住的部分根据引理就可以转化成：

注意到 $b_{j-1}+a_j=b_j$！因此：

框住的部分可以约分！我 tm 约约约约约！超级约分！成了 $\dfrac {b_{x-1}}{b_1}$。因此：

带回式子 $(8)$，得到：

注意到 $a_1=b_1$。带回式子 $(5)$，得到：

这下就算出期望深度了。好耶！

$\text{LCA}$ 的期望深度

这个部分才是最抽象的……

首先我们得到这样一个式子：

乍一看很对的样子。仔细一想，怎么来的？

（下面令 $z=\text{LCA}(x,y)$，可以理解成一个 define。）

首先我们可以发现，$\text{dep}(z)$ 与树的形态没有太大关系，仅与 $x,y,z$ 以及根结点有关。它们构成了一个 "$\lambda$" 字形结构，我们就只看它。这个结构又由两个部分构成：路径 $\Lambda=x-z-y$ 和路径 $\Iota=1-z$。对期望的贡献仅由 $1-z$ 构成，而概率则需考虑两个部分。也即：

由于每个点插入的顺序是一样的，因此每个点连接到另外一个点的概率是一样的。那么假若 $x,y,l$ 固定，$P(l=z)$ 也是一个定值。通过后续的证明我们也可以得到这一点。因此可以提出来：

因为 $x,y$ 已经确定， $\Lambda$ 形状的路径只用枚举 $l$。然后又发现 后面的部分就是 $E\big(\text{dep}(l)\big)$。因此：

回到正题。那么我们只用求 $P\big(l=\text{LCA}(x,y)\big)$ 即可。考虑这个 $\Lambda$ 形状的路径的概率，我们分两种情况讨论。

首先 $l=1$ 不需要考虑，因为 $l$ 的期望深度一定是 $0$。

不妨设 $x<y$。若 $x=y$，答案就是 $0$；如果 $x>y$，swap 两者即可。

情况一：$l\in(1,x)$

按照求期望深度的思路，我们可以得到路径 $l-x$ 单独的概率和 $l-y$ 单独的概率（注意两者略有不同）：

下者可以转化成（证明很简单，此处就略去了）：

既然知道了单独的概率，我们只要保证两个事件相互独立（也必须保证相互独立），就可以把两者概率相乘得到 $\Lambda$ 整体的概率。两个事件独立，在这里就是 $l-x$ 和 $l-y$ 上除了 $l$ 没有相同的点。由于建出来的是一棵树，我们能保证事件相互独立。

体现在公式中，就是要保证 $M\cap P=\varnothing$：

关于 $M$ 和 $P$，又可以转化成另一个问题。

给定一个数集 $S$，定义 $g(X)$ 表示集合 $S$ 内部所有元素的积。那么对于所有 $S$ 子集（包括空集）的 $g(X)$ 的和，就是 $\prod\limits_{i\in S} S_i+1$。

这是之前的引理。我们发现，倘若 $M\cup P$ 固定，$g(M)\cdot g(P)$ 就是固定的。那么问题变成在一个子集内再枚举一个子集了！也就是定义 $h(X)=g(X)\cdot(\text{所有子集个数})=g(X)\cdot 2^{|X|}$，求所有 $S$ 子集的 $h(X)$ 的和。

因此上面被框住的部分可以转化为，枚举一个子集 $S$，乘以 $2^{|S|}$：

因此：

根据引理，可以转化为：

到这里就好算了。

情况二：$l=x$

这个简单，刚才已经得到了（式子 $(20)$）：

根据引理可以化成：

对你没看错就是这么简单。

最终的处理

到这里就是解决实现的问题了。

令：

那么 $Ans=Part_1-2Part2$。

发现 $Part_2$ 与 $y$ 没有关系，因此可以预处理。

设：

可以发现：

从而可以做到线性预处理。即：

程序实现

Dsol

Dsol_fast